import java.util.*;

class Solution {
    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int ret = 0, sum = 0, n = startTime.length;
        for(int i = 0; i <= n; i++){
            sum += get(i, eventTime, startTime, endTime);
            if(i >= k){
                ret = Math.max(ret, sum);
                sum -= get(i - k, eventTime, startTime, endTime);
            }
        }
        return ret;
    }
    public int get(int i, int eventTime, int[] startTime, int[] endTime){
        if(i == 0){
            return startTime[0];
        }
        if(i == startTime.length){
            return eventTime - endTime[startTime.length - 1];
        }
        return startTime[i] - endTime[i - 1];
    }


    public int minSwaps(int[] nums) {
        int n = nums.length, one = 0;
        for(int i = 0; i < n; i++){
            if(nums[i] == 1) { one++;}
        }
        if(one == n || one == 0) { return 0;}

        int ret = Integer.MAX_VALUE, count = 0;
        for(int i = 0; i < n + one - 1; i++){
            if(nums[i % n] == 0) { count++;}
            if(i < one - 1) { continue;}
            ret = Math.min(ret, count);
            if(nums[(i - one + 1) % n] == 0) { count--;}
        }
        return ret;
    }


    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int n = s.length();
        char[] num = s.toCharArray();
        Map<String, Integer> str = new HashMap<>();
        Map<Character, Integer> ch = new HashMap<>();

        int ret = 0, count = 0;
        for(int i = 0; i < n; i++){
            ch.put(num[i], ch.getOrDefault(num[i], 0) + 1);
            if(ch.get(num[i]) == 1) { count++;}
            if(i < minSize - 1) { continue;}

            if(count <= maxLetters){
                String tmp = s.substring(i - minSize + 1, i + 1);
                str.put(tmp, str.getOrDefault(tmp, 0) + 1);
                ret = Math.max(ret, str.get(tmp));
            }
            ch.put(num[i - minSize + 1], ch.getOrDefault(num[i - minSize + 1], 0) - 1);
            if(ch.get(num[i - minSize + 1]) == 0){
                ch.remove(num[i - minSize + 1]);
                count--;
            }
        }
        return ret;
    }


    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        final int BIAS = 50;
        int[] tmp = new int[BIAS * 2 + 1];  //计数排序
        for(int i = 0; i < k - 1; i++){
            tmp[nums[i] + BIAS]++;
        }

        int n = nums.length;
        int[] ret = new int[n - k + 1];
        for(int i = k - 1; i < n; i++){
            tmp[nums[i] + BIAS]++;
            int left = x;  //第 x 大
            for(int j = 0; j < BIAS; j++){
                left -= tmp[j];
                if(left <= 0){
                    ret[i - k + 1] = j - BIAS;
                    break;
                }
            }
            tmp[nums[i - k + 1] + BIAS]--;
        }
        return ret;
    }
}